#include "kmp.h"
#include <iostream>
std::vector<int> getNext(std::string &pattern) {
  int i = 0, j = -1;
  std::vector<int> n = std::vector<int>(pattern.length(), -1);
  while (i < pattern.length()) {
    if (j == -1 || pattern[i] == pattern[j]) {
      i++;
      j++;
      n[i] = j;
    } else {
      j = n[j];
    }
  }
  return n;
}
int kmp(std::string &target, std::string &pattern) {
  int i = 0, j = 0;
  int pattern_size = pattern.length();
  std::vector<int> n(getNext(pattern));
  int s = pattern.length();
  while (i < target.length() && j < pattern.length()) {
    if (j == -1 || target[i] == pattern[j]) {
      i++;
      j++;
    } else {
      j = n[j];
    }
  }
  if (j == pattern.length()) {
    return i - j;
  } else {
    return -1;
  }
}
